<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span>
</span><span id="line-2"></span><span class="hs-pragma">{-# LANGUAGE BangPatterns #-}</span><span class="hs-cpp">
#ifdef __GLASGOW_HASKELL__
</span><span class="hs-pragma">{-# LANGUAGE Trustworthy #-}</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-7"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-8"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- Module      :  Data.Containers.ListUtils</span><span>
</span><span id="line-10"></span><span class="hs-comment">-- Copyright   :  (c) Gershom Bazerman 2018</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- License     :  BSD-style</span><span>
</span><span id="line-12"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-13"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-14"></span><span class="hs-comment">--</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- This module provides efficient containers-based functions on the list type.</span><span>
</span><span id="line-16"></span><span class="hs-comment">--</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- In the documentation, \(n\) is the number of elements in the list while</span><span>
</span><span id="line-18"></span><span class="hs-comment">-- \(d\) is the number of distinct elements in the list. \(W\) is the number</span><span>
</span><span id="line-19"></span><span class="hs-comment">-- of bits in an 'Int'.</span><span>
</span><span id="line-20"></span><span class="hs-comment">--</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- @since 0.6.0.1</span><span>
</span><span id="line-22"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-23"></span><span>
</span><span id="line-24"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.Containers.ListUtils</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-25"></span><span>       </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrd"><span class="hs-identifier">nubOrd</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-26"></span><span>       </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOn"><span class="hs-identifier">nubOrdOn</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-27"></span><span>       </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubInt"><span class="hs-identifier">nubInt</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-28"></span><span>       </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOn"><span class="hs-identifier">nubIntOn</span></a></span><span>
</span><span id="line-29"></span><span>       </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-30"></span><span>
</span><span id="line-31"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.Set.html"><span class="hs-identifier">Data.Set</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Set.Internal.html#Set"><span class="hs-identifier">Set</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-32"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="Data.Set.html"><span class="hs-identifier">Data.Set</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Set</span></span><span>
</span><span id="line-33"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="Data.IntSet.html"><span class="hs-identifier">Data.IntSet</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">IntSet</span></span><span>
</span><span id="line-34"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.IntSet.html"><span class="hs-identifier">Data.IntSet</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.IntSet.Internal.html#IntSet"><span class="hs-identifier">IntSet</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#ifdef __GLASGOW_HASKELL__
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/GHC.Exts.html#"><span class="hs-identifier">GHC.Exts</span></a></span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#build"><span class="hs-identifier">build</span></a></span><span> </span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-39"></span><span class="hs-comment">-- *** Ord-based nubbing ***</span><span>
</span><span id="line-40"></span><span>
</span><span id="line-41"></span><span>
</span><span id="line-42"></span><span class="hs-comment">-- | \( O(n \log d) \). The @nubOrd@ function removes duplicate elements from a</span><span>
</span><span id="line-43"></span><span class="hs-comment">-- list. In particular, it keeps only the first occurrence of each element. By</span><span>
</span><span id="line-44"></span><span class="hs-comment">-- using a 'Set' internally it has better asymptotics than the standard</span><span>
</span><span id="line-45"></span><span class="hs-comment">-- 'Data.List.nub' function.</span><span>
</span><span id="line-46"></span><span class="hs-comment">--</span><span>
</span><span id="line-47"></span><span class="hs-comment">-- ==== Strictness</span><span>
</span><span id="line-48"></span><span class="hs-comment">--</span><span>
</span><span id="line-49"></span><span class="hs-comment">-- @nubOrd@ is strict in the elements of the list.</span><span>
</span><span id="line-50"></span><span class="hs-comment">--</span><span>
</span><span id="line-51"></span><span class="hs-comment">-- ==== Efficiency note</span><span>
</span><span id="line-52"></span><span class="hs-comment">--</span><span>
</span><span id="line-53"></span><span class="hs-comment">-- When applicable, it is almost always better to use 'nubInt' or 'nubIntOn'</span><span>
</span><span id="line-54"></span><span class="hs-comment">-- instead of this function, although it can be a little worse in certain</span><span>
</span><span id="line-55"></span><span class="hs-comment">-- pathological cases. For example, to nub a list of characters, use</span><span>
</span><span id="line-56"></span><span class="hs-comment">--</span><span>
</span><span id="line-57"></span><span class="hs-comment">-- @ nubIntOn fromEnum xs @</span><span>
</span><span id="line-58"></span><span class="hs-comment">--</span><span>
</span><span id="line-59"></span><span class="hs-comment">-- @since 0.6.0.1</span><span>
</span><span id="line-60"></span><span id="local-6989586621679180566"><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrd"><span class="hs-identifier hs-type">nubOrd</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679180566"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180566"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180566"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-61"></span><span id="nubOrd"><span class="annot"><span class="annottext">nubOrd :: forall a. Ord a =&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubOrd"><span class="hs-identifier hs-var hs-var">nubOrd</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; a) -&gt; [a] -&gt; [a]
forall b a. Ord b =&gt; (a -&gt; b) -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubOrdOn"><span class="hs-identifier hs-var">nubOrdOn</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; a
forall a. a -&gt; a
</span><a href="../../base/src/GHC.Base.html#id"><span class="hs-identifier hs-var">id</span></a></span><span>
</span><span id="line-62"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrd"><span class="hs-pragma hs-type">nubOrd</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-63"></span><span>
</span><span id="line-64"></span><span class="hs-comment">-- | The @nubOrdOn@ function behaves just like 'nubOrd' except it performs</span><span>
</span><span id="line-65"></span><span class="hs-comment">-- comparisons not on the original datatype, but a user-specified projection</span><span>
</span><span id="line-66"></span><span class="hs-comment">-- from that datatype.</span><span>
</span><span id="line-67"></span><span class="hs-comment">--</span><span>
</span><span id="line-68"></span><span class="hs-comment">-- ==== Strictness</span><span>
</span><span id="line-69"></span><span class="hs-comment">--</span><span>
</span><span id="line-70"></span><span class="hs-comment">-- @nubOrdOn@ is strict in the values of the function applied to the</span><span>
</span><span id="line-71"></span><span class="hs-comment">-- elements of the list.</span><span>
</span><span id="line-72"></span><span class="hs-comment">--</span><span>
</span><span id="line-73"></span><span class="hs-comment">-- @since 0.6.0.1</span><span>
</span><span id="line-74"></span><span id="local-6989586621679180563"><span id="local-6989586621679180564"><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOn"><span class="hs-identifier hs-type">nubOrdOn</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679180564"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180563"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180564"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180563"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180563"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span></span><span>
</span><span id="line-75"></span><span class="hs-comment">-- For some reason we need to write an explicit lambda here to allow this</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- to inline when only applied to a function.</span><span>
</span><span id="line-77"></span><span id="nubOrdOn"><span class="annot"><span class="annottext">nubOrdOn :: forall b a. Ord b =&gt; (a -&gt; b) -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubOrdOn"><span class="hs-identifier hs-var hs-var">nubOrdOn</span></a></span></span><span> </span><span id="local-6989586621679180522"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180522"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-glyph">\</span><span id="local-6989586621679180521"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180521"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">(a -&gt; b) -&gt; Set b -&gt; [a] -&gt; [a]
forall b a. Ord b =&gt; (a -&gt; b) -&gt; Set b -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-identifier hs-var">nubOrdOnExcluding</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180522"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
forall a. Set a
</span><a href="Data.Set.Internal.html#empty"><span class="hs-identifier hs-var">Set.empty</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180521"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-78"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOn"><span class="hs-pragma hs-type">nubOrdOn</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-79"></span><span>
</span><span id="line-80"></span><span class="hs-comment">-- Splitting nubOrdOn like this means that we don't have to worry about</span><span>
</span><span id="line-81"></span><span class="hs-comment">-- matching specifically on Set.empty in the rewrite-back rule.</span><span>
</span><span id="line-82"></span><span id="local-6989586621679180557"><span id="local-6989586621679180558"><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-identifier hs-type">nubOrdOnExcluding</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679180558"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180557"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180558"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Set.Internal.html#Set"><span class="hs-identifier hs-type">Set</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180558"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180557"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180557"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span></span><span>
</span><span id="line-83"></span><span id="nubOrdOnExcluding"><span class="annot"><span class="annottext">nubOrdOnExcluding :: forall b a. Ord b =&gt; (a -&gt; b) -&gt; Set b -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-identifier hs-var hs-var">nubOrdOnExcluding</span></a></span></span><span> </span><span id="local-6989586621679180517"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180517"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set b -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180516"><span class="hs-identifier hs-var">go</span></a></span><span>
</span><span id="line-84"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-85"></span><span>    </span><span id="local-6989586621679180516"><span class="annot"><span class="annottext">go :: Set b -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180516"><span class="hs-identifier hs-var hs-var">go</span></a></span></span><span> </span><span class="annot"><span class="annottext">Set b
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-86"></span><span>    </span><span class="annot"><a href="#local-6989586621679180516"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span id="local-6989586621679180513"><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180513"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679180512"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180512"><span class="hs-identifier hs-var">x</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621679180511"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180511"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-87"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679180510"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; Set b -&gt; Bool
forall a. Ord a =&gt; a -&gt; Set a -&gt; Bool
</span><a href="Data.Set.Internal.html#member"><span class="hs-operator hs-var">`Set.member`</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180513"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set b -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180516"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180513"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180511"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-88"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180512"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">Set b -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180516"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b -&gt; Set b -&gt; Set b
forall a. Ord a =&gt; a -&gt; Set a -&gt; Set a
</span><a href="Data.Set.Internal.html#insert"><span class="hs-identifier hs-var">Set.insert</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679180510"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180513"><span class="hs-identifier hs-var">s</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180511"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-89"></span><span>      </span><span class="hs-keyword">where</span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679180510"><span class="annot"><span class="annottext">fx :: b
</span><a href="#local-6989586621679180510"><span class="hs-identifier hs-var hs-var">fx</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180517"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180512"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-cpp">

#ifdef __GLASGOW_HASKELL__
</span><span class="hs-comment">-- We want this inlinable to specialize to the necessary Ord instance.</span><span>
</span><span id="line-93"></span><span class="hs-pragma">{-# INLINABLE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-pragma hs-type">nubOrdOnExcluding</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-94"></span><span>
</span><span id="line-95"></span><span class="hs-pragma">{-# RULES</span><span>
</span><span id="line-96"></span><span class="hs-pragma">-- Rewrite to a fusible form.</span><span>
</span><span id="line-97"></span><span class="annot"><span class="hs-pragma">&quot;nubOrdOn&quot;</span></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">~</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="hs-pragma">forall</span><span> </span><span id="local-6989586621679180507"><span class="annot"><a href="#local-6989586621679180507"><span class="hs-pragma hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180506"><span class="annot"><a href="#local-6989586621679180506"><span class="hs-pragma hs-var">as</span></a></span></span><span> </span><span id="local-6989586621679180505"><span class="annot"><a href="#local-6989586621679180505"><span class="hs-pragma hs-var">s</span></a></span></span><span class="hs-pragma">.</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-pragma hs-type">nubOrdOnExcluding</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621679180507"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180505"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180506"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="hs-pragma">=</span><span>
</span><span id="line-98"></span><span>  </span><span class="annot"><a href="../../base/src/GHC.Base.html#build"><span class="hs-pragma hs-type">build</span></a></span><span> </span><span class="hs-pragma">(</span><span class="hs-pragma">\</span><span id="local-6989586621679180504"><span class="annot"><a href="#local-6989586621679180504"><span class="hs-pragma hs-var">c</span></a></span></span><span> </span><span id="local-6989586621679180503"><span class="annot"><a href="#local-6989586621679180503"><span class="hs-pragma hs-var">n</span></a></span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-pragma hs-type">foldr</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnFB"><span class="hs-pragma hs-type">nubOrdOnFB</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180507"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180504"><span class="hs-pragma hs-type">c</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-pragma hs-type">constNubOn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180503"><span class="hs-pragma hs-type">n</span></a></span><span class="hs-pragma">)</span><span> </span><span class="annot"><a href="#local-6989586621679180506"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180505"><span class="hs-pragma hs-type">s</span></a></span><span class="hs-pragma">)</span><span>
</span><span id="line-99"></span><span>
</span><span id="line-100"></span><span class="hs-pragma">-- Rewrite back to a plain form</span><span>
</span><span id="line-101"></span><span class="annot"><span class="hs-pragma">&quot;nubOrdOnList&quot;</span></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="hs-pragma">forall</span><span> </span><span id="local-6989586621679180499"><span class="annot"><a href="#local-6989586621679180499"><span class="hs-pragma hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180498"><span class="annot"><a href="#local-6989586621679180498"><span class="hs-pragma hs-var">as</span></a></span></span><span> </span><span id="local-6989586621679180497"><span class="annot"><a href="#local-6989586621679180497"><span class="hs-pragma hs-var">s</span></a></span></span><span class="hs-pragma">.</span><span>
</span><span id="line-102"></span><span>    </span><span class="annot"><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-pragma hs-type">foldr</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnFB"><span class="hs-pragma hs-type">nubOrdOnFB</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180499"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="hs-pragma">(</span><span class="hs-pragma">:</span><span class="hs-pragma">)</span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-pragma hs-type">constNubOn</span></a></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">]</span><span class="hs-pragma">)</span><span> </span><span class="annot"><a href="#local-6989586621679180498"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180497"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="hs-pragma">=</span><span>
</span><span id="line-103"></span><span>       </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnExcluding"><span class="hs-pragma hs-type">nubOrdOnExcluding</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180499"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180497"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180498"><span class="hs-pragma hs-type">as</span></a></span><span>
</span><span id="line-104"></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-105"></span><span>
</span><span id="line-106"></span><span id="local-6989586621679180548"><span id="local-6989586621679180549"><span id="local-6989586621679180550"><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnFB"><span class="hs-identifier hs-type">nubOrdOnFB</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679180550"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-107"></span><span>           </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180549"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180550"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-108"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180549"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180548"><span class="hs-identifier hs-type">r</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180548"><span class="hs-identifier hs-type">r</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-109"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180549"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-110"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Set.Internal.html#Set"><span class="hs-identifier hs-type">Set</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180550"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180548"><span class="hs-identifier hs-type">r</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-111"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Set.Internal.html#Set"><span class="hs-identifier hs-type">Set</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180550"><span class="hs-identifier hs-type">b</span></a></span><span>
</span><span id="line-112"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180548"><span class="hs-identifier hs-type">r</span></a></span></span></span></span><span>
</span><span id="line-113"></span><span id="nubOrdOnFB"><span class="annot"><span class="annottext">nubOrdOnFB :: forall b a r.
Ord b =&gt;
(a -&gt; b) -&gt; (a -&gt; r -&gt; r) -&gt; a -&gt; (Set b -&gt; r) -&gt; Set b -&gt; r
</span><a href="Data.Containers.ListUtils.html#nubOrdOnFB"><span class="hs-identifier hs-var hs-var">nubOrdOnFB</span></a></span></span><span> </span><span id="local-6989586621679180493"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180493"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180492"><span class="annot"><span class="annottext">a -&gt; r -&gt; r
</span><a href="#local-6989586621679180492"><span class="hs-identifier hs-var">c</span></a></span></span><span> </span><span id="local-6989586621679180491"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180491"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679180490"><span class="annot"><span class="annottext">Set b -&gt; r
</span><a href="#local-6989586621679180490"><span class="hs-identifier hs-var">r</span></a></span></span><span> </span><span id="local-6989586621679180489"><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180489"><span class="hs-identifier hs-var">s</span></a></span></span><span>
</span><span id="line-114"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679180488"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; Set b -&gt; Bool
forall a. Ord a =&gt; a -&gt; Set a -&gt; Bool
</span><a href="Data.Set.Internal.html#member"><span class="hs-operator hs-var">`Set.member`</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180489"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set b -&gt; r
</span><a href="#local-6989586621679180490"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180489"><span class="hs-identifier hs-var">s</span></a></span><span>
</span><span id="line-115"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180491"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; r -&gt; r
</span><a href="#local-6989586621679180492"><span class="hs-operator hs-var">`c`</span></a></span><span> </span><span class="annot"><span class="annottext">Set b -&gt; r
</span><a href="#local-6989586621679180490"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b -&gt; Set b -&gt; Set b
forall a. Ord a =&gt; a -&gt; Set a -&gt; Set a
</span><a href="Data.Set.Internal.html#insert"><span class="hs-identifier hs-var">Set.insert</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679180488"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">Set b
</span><a href="#local-6989586621679180489"><span class="hs-identifier hs-var">s</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-116"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679180488"><span class="annot"><span class="annottext">fx :: b
</span><a href="#local-6989586621679180488"><span class="hs-identifier hs-var hs-var">fx</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679180493"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180491"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-117"></span><span class="hs-pragma">{-# INLINABLE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">0</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubOrdOnFB"><span class="hs-pragma hs-type">nubOrdOnFB</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-118"></span><span>
</span><span id="line-119"></span><span id="local-6989586621679180543"><span id="local-6989586621679180544"><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-identifier hs-type">constNubOn</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621679180544"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180543"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180544"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-120"></span><span id="constNubOn"><span class="annot"><span class="annottext">constNubOn :: forall a b. a -&gt; b -&gt; a
</span><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-identifier hs-var hs-var">constNubOn</span></a></span></span><span> </span><span id="local-6989586621679180487"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180487"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="annot"><span class="annottext">b
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180487"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-121"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">0</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-pragma hs-type">constNubOn</span></a></span><span> </span><span class="hs-pragma">#-}</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-124"></span><span>
</span><span id="line-125"></span><span class="hs-comment">-- *** Int-based nubbing ***</span><span>
</span><span id="line-126"></span><span>
</span><span id="line-127"></span><span>
</span><span id="line-128"></span><span class="hs-comment">-- | \( O(n \min(d,W)) \). The @nubInt@ function removes duplicate 'Int'</span><span>
</span><span id="line-129"></span><span class="hs-comment">-- values from a list. In particular, it keeps only the first occurrence</span><span>
</span><span id="line-130"></span><span class="hs-comment">-- of each element. By using an 'IntSet' internally, it attains better</span><span>
</span><span id="line-131"></span><span class="hs-comment">-- asymptotics than the standard 'Data.List.nub' function.</span><span>
</span><span id="line-132"></span><span class="hs-comment">--</span><span>
</span><span id="line-133"></span><span class="hs-comment">-- See also 'nubIntOn', a more widely applicable generalization.</span><span>
</span><span id="line-134"></span><span class="hs-comment">--</span><span>
</span><span id="line-135"></span><span class="hs-comment">-- ==== Strictness</span><span>
</span><span id="line-136"></span><span class="hs-comment">--</span><span>
</span><span id="line-137"></span><span class="hs-comment">-- @nubInt@ is strict in the elements of the list.</span><span>
</span><span id="line-138"></span><span class="hs-comment">--</span><span>
</span><span id="line-139"></span><span class="hs-comment">-- @since 0.6.0.1</span><span>
</span><span id="line-140"></span><span class="annot"><a href="Data.Containers.ListUtils.html#nubInt"><span class="hs-identifier hs-type">nubInt</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">]</span><span>
</span><span id="line-141"></span><span id="nubInt"><span class="annot"><span class="annottext">nubInt :: [Int] -&gt; [Int]
</span><a href="Data.Containers.ListUtils.html#nubInt"><span class="hs-identifier hs-var hs-var">nubInt</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Int -&gt; Int) -&gt; [Int] -&gt; [Int]
forall a. (a -&gt; Int) -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubIntOn"><span class="hs-identifier hs-var">nubIntOn</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int
forall a. a -&gt; a
</span><a href="../../base/src/GHC.Base.html#id"><span class="hs-identifier hs-var">id</span></a></span><span>
</span><span id="line-142"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubInt"><span class="hs-pragma hs-type">nubInt</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-143"></span><span>
</span><span id="line-144"></span><span class="hs-comment">-- | The @nubIntOn@ function behaves just like 'nubInt' except it performs</span><span>
</span><span id="line-145"></span><span class="hs-comment">-- comparisons not on the original datatype, but a user-specified projection</span><span>
</span><span id="line-146"></span><span class="hs-comment">-- from that datatype. For example, @nubIntOn 'fromEnum'@ can be used to</span><span>
</span><span id="line-147"></span><span class="hs-comment">-- nub characters and typical fixed-with numerical types efficiently.</span><span>
</span><span id="line-148"></span><span class="hs-comment">--</span><span>
</span><span id="line-149"></span><span class="hs-comment">-- ==== Strictness</span><span>
</span><span id="line-150"></span><span class="hs-comment">--</span><span>
</span><span id="line-151"></span><span class="hs-comment">-- @nubIntOn@ is strict in the values of the function applied to the</span><span>
</span><span id="line-152"></span><span class="hs-comment">-- elements of the list.</span><span>
</span><span id="line-153"></span><span class="hs-comment">--</span><span>
</span><span id="line-154"></span><span class="hs-comment">-- @since 0.6.0.1</span><span>
</span><span id="line-155"></span><span id="local-6989586621679180540"><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOn"><span class="hs-identifier hs-type">nubIntOn</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180540"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180540"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180540"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-156"></span><span class="hs-comment">-- For some reason we need to write an explicit lambda here to allow this</span><span>
</span><span id="line-157"></span><span class="hs-comment">-- to inline when only applied to a function.</span><span>
</span><span id="line-158"></span><span id="nubIntOn"><span class="annot"><span class="annottext">nubIntOn :: forall a. (a -&gt; Int) -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubIntOn"><span class="hs-identifier hs-var hs-var">nubIntOn</span></a></span></span><span> </span><span id="local-6989586621679180486"><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180486"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-glyph">\</span><span id="local-6989586621679180485"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180485"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Int) -&gt; IntSet -&gt; [a] -&gt; [a]
forall a. (a -&gt; Int) -&gt; IntSet -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-identifier hs-var">nubIntOnExcluding</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180486"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="Data.IntSet.Internal.html#empty"><span class="hs-identifier hs-var">IntSet.empty</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180485"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-159"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOn"><span class="hs-pragma hs-type">nubIntOn</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-160"></span><span>
</span><span id="line-161"></span><span class="hs-comment">-- Splitting nubIntOn like this means that we don't have to worry about</span><span>
</span><span id="line-162"></span><span class="hs-comment">-- matching specifically on IntSet.empty in the rewrite-back rule.</span><span>
</span><span id="line-163"></span><span id="local-6989586621679180537"><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-identifier hs-type">nubIntOnExcluding</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180537"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#IntSet"><span class="hs-identifier hs-type">IntSet</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180537"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679180537"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-164"></span><span id="nubIntOnExcluding"><span class="annot"><span class="annottext">nubIntOnExcluding :: forall a. (a -&gt; Int) -&gt; IntSet -&gt; [a] -&gt; [a]
</span><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-identifier hs-var hs-var">nubIntOnExcluding</span></a></span></span><span> </span><span id="local-6989586621679180482"><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180482"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntSet -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180481"><span class="hs-identifier hs-var">go</span></a></span><span>
</span><span id="line-165"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-166"></span><span>    </span><span id="local-6989586621679180481"><span class="annot"><span class="annottext">go :: IntSet -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180481"><span class="hs-identifier hs-var hs-var">go</span></a></span></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-167"></span><span>    </span><span class="annot"><a href="#local-6989586621679180481"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span id="local-6989586621679180480"><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180480"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679180479"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180479"><span class="hs-identifier hs-var">x</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621679180478"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180478"><span class="hs-identifier hs-var">xs</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-168"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679180477"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; IntSet -&gt; Bool
</span><a href="Data.IntSet.Internal.html#member"><span class="hs-operator hs-var">`IntSet.member`</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180480"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntSet -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180481"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180480"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180478"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-169"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180479"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">IntSet -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679180481"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; IntSet -&gt; IntSet
</span><a href="Data.IntSet.Internal.html#insert"><span class="hs-identifier hs-var">IntSet.insert</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679180477"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180480"><span class="hs-identifier hs-var">s</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679180478"><span class="hs-identifier hs-var">xs</span></a></span><span>
</span><span id="line-170"></span><span>      </span><span class="hs-keyword">where</span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679180477"><span class="annot"><span class="annottext">fx :: Int
</span><a href="#local-6989586621679180477"><span class="hs-identifier hs-var hs-var">fx</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180482"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180479"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-cpp">

#ifdef __GLASGOW_HASKELL__
</span><span class="hs-comment">-- We don't mark this INLINABLE because it doesn't seem obviously useful</span><span>
</span><span id="line-174"></span><span class="hs-comment">-- to inline it anywhere; the elements the function operates on are actually</span><span>
</span><span id="line-175"></span><span class="hs-comment">-- pulled from a list and installed in a list; the situation is very different</span><span>
</span><span id="line-176"></span><span class="hs-comment">-- when fusion occurs. In this case, we let GHC make the call.</span><span>
</span><span id="line-177"></span><span class="hs-pragma">{-# NOINLINE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-pragma hs-type">nubIntOnExcluding</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-178"></span><span>
</span><span id="line-179"></span><span class="hs-pragma">{-# RULES</span><span>
</span><span id="line-180"></span><span class="annot"><span class="hs-pragma">&quot;nubIntOn&quot;</span></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">~</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="hs-pragma">forall</span><span> </span><span id="local-6989586621679180474"><span class="annot"><a href="#local-6989586621679180474"><span class="hs-pragma hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180473"><span class="annot"><a href="#local-6989586621679180473"><span class="hs-pragma hs-var">as</span></a></span></span><span> </span><span id="local-6989586621679180472"><span class="annot"><a href="#local-6989586621679180472"><span class="hs-pragma hs-var">s</span></a></span></span><span class="hs-pragma">.</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-pragma hs-type">nubIntOnExcluding</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621679180474"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180472"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180473"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="hs-pragma">=</span><span>
</span><span id="line-181"></span><span>  </span><span class="annot"><a href="../../base/src/GHC.Base.html#build"><span class="hs-pragma hs-type">build</span></a></span><span> </span><span class="hs-pragma">(</span><span class="hs-pragma">\</span><span id="local-6989586621679180471"><span class="annot"><a href="#local-6989586621679180471"><span class="hs-pragma hs-var">c</span></a></span></span><span> </span><span id="local-6989586621679180470"><span class="annot"><a href="#local-6989586621679180470"><span class="hs-pragma hs-var">n</span></a></span></span><span> </span><span class="hs-pragma">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-pragma hs-type">foldr</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnFB"><span class="hs-pragma hs-type">nubIntOnFB</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180474"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180471"><span class="hs-pragma hs-type">c</span></a></span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-pragma hs-type">constNubOn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180470"><span class="hs-pragma hs-type">n</span></a></span><span class="hs-pragma">)</span><span> </span><span class="annot"><a href="#local-6989586621679180473"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180472"><span class="hs-pragma hs-type">s</span></a></span><span class="hs-pragma">)</span><span>
</span><span id="line-182"></span><span class="annot"><span class="hs-pragma">&quot;nubIntOnList&quot;</span></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="hs-pragma">forall</span><span> </span><span id="local-6989586621679180468"><span class="annot"><a href="#local-6989586621679180468"><span class="hs-pragma hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180467"><span class="annot"><a href="#local-6989586621679180467"><span class="hs-pragma hs-var">as</span></a></span></span><span> </span><span id="local-6989586621679180466"><span class="annot"><a href="#local-6989586621679180466"><span class="hs-pragma hs-var">s</span></a></span></span><span class="hs-pragma">.</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-pragma hs-type">foldr</span></a></span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnFB"><span class="hs-pragma hs-type">nubIntOnFB</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180468"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="hs-pragma">(</span><span class="hs-pragma">:</span><span class="hs-pragma">)</span><span class="hs-pragma">)</span><span> </span><span class="hs-pragma">(</span><span class="annot"><a href="Data.Containers.ListUtils.html#constNubOn"><span class="hs-pragma hs-type">constNubOn</span></a></span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">]</span><span class="hs-pragma">)</span><span> </span><span class="annot"><a href="#local-6989586621679180467"><span class="hs-pragma hs-type">as</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180466"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="hs-pragma">=</span><span>
</span><span id="line-183"></span><span>  </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnExcluding"><span class="hs-pragma hs-type">nubIntOnExcluding</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180468"><span class="hs-pragma hs-type">f</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180466"><span class="hs-pragma hs-type">s</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679180467"><span class="hs-pragma hs-type">as</span></a></span><span>
</span><span id="line-184"></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-185"></span><span>
</span><span id="line-186"></span><span id="local-6989586621679180534"><span id="local-6989586621679180535"><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnFB"><span class="hs-identifier hs-type">nubIntOnFB</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180535"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-special">)</span><span>
</span><span id="line-187"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679180535"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180534"><span class="hs-identifier hs-type">r</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180534"><span class="hs-identifier hs-type">r</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-188"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180535"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-189"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.IntSet.Internal.html#IntSet"><span class="hs-identifier hs-type">IntSet</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180534"><span class="hs-identifier hs-type">r</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-190"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#IntSet"><span class="hs-identifier hs-type">IntSet</span></a></span><span>
</span><span id="line-191"></span><span>           </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679180534"><span class="hs-identifier hs-type">r</span></a></span></span></span><span>
</span><span id="line-192"></span><span id="nubIntOnFB"><span class="annot"><span class="annottext">nubIntOnFB :: forall a r.
(a -&gt; Int) -&gt; (a -&gt; r -&gt; r) -&gt; a -&gt; (IntSet -&gt; r) -&gt; IntSet -&gt; r
</span><a href="Data.Containers.ListUtils.html#nubIntOnFB"><span class="hs-identifier hs-var hs-var">nubIntOnFB</span></a></span></span><span> </span><span id="local-6989586621679180465"><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180465"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679180464"><span class="annot"><span class="annottext">a -&gt; r -&gt; r
</span><a href="#local-6989586621679180464"><span class="hs-identifier hs-var">c</span></a></span></span><span> </span><span id="local-6989586621679180463"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180463"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679180462"><span class="annot"><span class="annottext">IntSet -&gt; r
</span><a href="#local-6989586621679180462"><span class="hs-identifier hs-var">r</span></a></span></span><span> </span><span id="local-6989586621679180461"><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180461"><span class="hs-identifier hs-var">s</span></a></span></span><span>
</span><span id="line-193"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679180460"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; IntSet -&gt; Bool
</span><a href="Data.IntSet.Internal.html#member"><span class="hs-operator hs-var">`IntSet.member`</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180461"><span class="hs-identifier hs-var">s</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntSet -&gt; r
</span><a href="#local-6989586621679180462"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180461"><span class="hs-identifier hs-var">s</span></a></span><span>
</span><span id="line-194"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180463"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; r -&gt; r
</span><a href="#local-6989586621679180464"><span class="hs-operator hs-var">`c`</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet -&gt; r
</span><a href="#local-6989586621679180462"><span class="hs-identifier hs-var">r</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int -&gt; IntSet -&gt; IntSet
</span><a href="Data.IntSet.Internal.html#insert"><span class="hs-identifier hs-var">IntSet.insert</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679180460"><span class="hs-identifier hs-var">fx</span></a></span><span> </span><span class="annot"><span class="annottext">IntSet
</span><a href="#local-6989586621679180461"><span class="hs-identifier hs-var">s</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-195"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679180460"><span class="annot"><span class="annottext">fx :: Int
</span><a href="#local-6989586621679180460"><span class="hs-identifier hs-var hs-var">fx</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; Int
</span><a href="#local-6989586621679180465"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679180463"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-196"></span><span class="hs-pragma">{-# INLINABLE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">0</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Containers.ListUtils.html#nubIntOnFB"><span class="hs-pragma hs-type">nubIntOnFB</span></a></span><span> </span><span class="hs-pragma">#-}</span><span class="hs-cpp">
#endif
</span></pre></body></html>